#include <bits/stdc++.h>
#include <sys/time.h>
#include "Graph.hpp"
#include <unistd.h>

using namespace std;

// TEST DEMO
/*
7 12
1 2 2
1 4 1
3 1 4
2 4 3
2 5 10
4 3 2
4 5 2
3 6 5
4 6 8
4 7 4
5 7 6
7 6 1
*/

int main()
{
    struct timeval t1, t2;
    int vertexNum, edgeNum;
    cin >> vertexNum >> edgeNum;
    Graph g{vertexNum};
    for(int i = 0; i < edgeNum; ++i) {
        int s, e, w;
        cin >> s >> e >> w;
        g.addEdge(s - 1, e - 1, w);
    }
    int s;
    cin >> s;
    gettimeofday(&t1, NULL);
    g.dijkstra(s - 1);
    gettimeofday(&t2, NULL);
    cout << "Cost Time: " << (t2.tv_sec-t1.tv_sec) * 1000000 + t2.tv_usec-t1.tv_usec << "us" << endl;
    return 0;
}